#include "Convex.h"

Convex::Convex(void)
{
   m_points           = new figPoints();
   m_edgeList         = new edgeList();
   m_vertQueue        = new vertQueue();
   m_helper           = new Helper();
   m_faceFactory      = new FaceFactory();
   m_edgeList4Search  = new diagonalMap();
}

Convex::~Convex(void)
{
  this->Clean();
  delete(m_edgeList);
  delete(m_vertQueue);
  delete(m_points);
  delete(m_helper);
  delete(m_faceFactory);
  delete(m_edgeList4Search);
}

void Convex::Clean()
{
  figPointsIterator it;
  for(it = m_points->begin(); 
      it != m_points->end();
          it++)
  {
    delete(reinterpret_cast<figureVertice *>(*it));
  }
  
  edgeIterator it2;
  for(it = m_edgeList->begin();
      it != m_edgeList->end();
      it++)
  {
    delete(reinterpret_cast<figureEdge *>(*it));
  }
}


const figureEdge & Convex::FindEdge(const figureVertice & v, bool direction)
{
  edgeIterator it;
  figureEdge    *e;
  figureVertice vert;
  for(it = m_edgeList->begin();
      it != m_edgeList->end();
      it++)
  {
    e = reinterpret_cast<figureEdge *>(*it);
    vert = (direction)?e->_begin:e->_end;
    if(vert == v)
    {
      return (*e);
    }
  } 
  //return (m_edgeList->end());
}

const edgeIterator & Convex::FindEdgeIter(const figureVertice & v)
{
  figureEdge    *e;
  for(m_edgeIter = m_edgeList->begin();
      m_edgeIter != m_edgeList->end();
      m_edgeIter++)
  {
    e = reinterpret_cast<figureEdge *>(*m_edgeIter);
    if(e->_begin == v)
    {
      return m_edgeIter;
    }
  }
  return (m_edgeList->end());
}


verticeType  Convex::CheckVertexType(const figureVertice & prev, const figureVertice & current,const figureVertice & next) //Three point prev, current, next
{
  //Start vertice is when the left and right neigbours are lie below this vertices (so only y-coordinate is important

  //The algorithm is very simple 
  //We create a vector c which is product of two vectors
  //The C vector is working in third dimension
  //So we add an extra dimension
  //the coordinate of c vector inform us about angle turning (clockwise or counterclockwise) 
  double interior_angle = 0.0;

  Vector2D v1(prev,current);
  Vector2D v2(current,next);
  
  interior_angle = v1.GetFollowVectorAngle(v2,true);
  
  if(((current.y > prev.y) && (current.y >= next.y)) ||
     ((current.y >= prev.y) && (current.y > next.y)))
  {
    if(interior_angle < 180)
      return (_startVert);
    else
      return (_splitVert);
  }
  if(((current.y < prev.y) && (current.y < next.y)) ||
     ((current.y < prev.y) && (current.y <= next.y)))
  {
    if(interior_angle > 180)
      return (_mergeVert);
    else
      return (_endVert);
  }
  return (_regularVert);
}




void Convex::CreateEdges(const HWND & hwnd, CFigure2D * figure, POINT & shift)
{
  //From figure we take all points
  //and create edges doubly-connected list
  //Firstly we have to find a starting point where the y-coordinates 
  int           loop = 0;
  int           size = 0;
  figureEdge   *fgEdge, *prev = NULL;
  figureVertice _pt_beg,_pt;
  bool          clockwise = true;
  
  m_hWnd  = hwnd;
  m_shift = shift;
  //m_figure = figure;

  m_edgeList->clear();

  _pt_beg = figure->GetFirstPoint();
  //Check counter clockwise of figure
  //and create a edges with counter clockwise schema
  _pt = figure->GetNextPoint();

  if(_pt_beg.x < _pt.x)
    clockwise = false;
  //
  clockwise = figure->GetCirculation();
  //CheckDirection(_pt_beg,_pt);

  _pt_beg = (clockwise)?figure->GetFirstPoint():figure->GetLastPoint();
  size = figure->GetSize() - 1; //the count of edges equals points count - 1, because the last point is equal to first one 
  for(loop; loop < size; loop++)
  {
    if(clockwise)
      _pt = figure->GetNextPoint();
    else
      _pt = figure->GetPrevPoint();

    fgEdge = new figureEdge();
    fgEdge->_begin = _pt_beg;
    fgEdge->_end   = _pt;
    fgEdge->_order = loop;
    
    if(prev)
    {
      fgEdge->prev   = prev;
      prev->next = fgEdge;
      fgEdge->_begin._type = CheckVertexType(prev->_begin,fgEdge->_begin,fgEdge->_end);
    }
    m_edgeList->push_back((long long)fgEdge);
        
    prev = fgEdge;
    _pt_beg = _pt;
  }

  prev->next = reinterpret_cast<figureEdge *>(m_edgeList->front());
  prev->next->prev = reinterpret_cast<figureEdge *>(prev);

  //m_edgeList4Search = m_edgeList;

  CreateVerticesListAndQueue();
}

void Convex::CreateVerticesListAndQueue()
{
  //Now based on edge list we should create a sorted (priority) 
  //verices list and add to each vertices special type

  //So we take each point from edge (only _begin point)
  //wi will check whic point has a bigger priority
  //It is like a tree building
  int loop      = 0;
  int size      = m_edgeList->size();
  int priority  = size; //from 1 to n
  figureVertice * curr,*prev = NULL;
  edgeIterator    m_edgeIter;
  
  m_points->clear();

  prev = &(reinterpret_cast<figureEdge *>(m_edgeList->back()))->_begin;
  for(m_edgeIter = m_edgeList->begin(); 
      m_edgeIter != m_edgeList->end();
      m_edgeIter++)
  {
    curr = new figureVertice();

    *curr = (reinterpret_cast<figureEdge *>(*m_edgeIter))->_begin;
    curr->_type = CheckVertexType(*prev,*curr,(reinterpret_cast<figureEdge *>(*m_edgeIter))->_end);
   
    //Now we fill the doubly-oriented list    
    if(prev)
    {
      curr->prev = prev;
      prev->next = curr;
    }
    m_points->push_back((long long)curr);
    prev = curr;
  }

  //Now we have to fill the first point of prev pointer to last one :)
  reinterpret_cast<figureVertice *> (m_points->front())->prev = curr;
  reinterpret_cast<figureVertice *> (m_points->back())->next = reinterpret_cast<figureVertice *> (m_points->front());
  
  //Now we can fill the sorted queue
  
  
  figPoints::iterator it;
  figureVertice * vt;
  for(it = m_points->begin(); 
      it != m_points->end();
          it++)
  {
    vt = reinterpret_cast<figureVertice *>(*it);
    m_vertQueue->push(*(reinterpret_cast<figureVertice *>(*it)));
    
  }

#ifdef DEBUG
  
  
   figureVertice v;
   figureEdge    e;
   while(!m_vertQueue->empty())
   {
     v = m_vertQueue->top();
     m_vertQueue->pop();
     e = FindEdge(v,true);
     HandleVertex(v,e);
   }
#endif
   
  
  //Now we have a point list
  SplitFigure2Face();
}


void Convex::HandleVertex(const figureVertice & vt, const figureEdge & edge)
{
  figureEdge    fe;
  figureVertice v;
  switch(vt._type)
  {
    case _startVert:
      {
        m_helper->AddEdgeBT(edge);
        m_helper->UpdateEgde(edge, vt);
      }break;
    case _endVert:
      {
        v = m_helper->GetHelper(*edge.prev);
        if(v._type == _mergeVert)
        {
          fe._begin = vt;
          fe._end   = v;
          //m_diagonals.push_back(fe);
          m_diagonals.insert(fe);
        }
        m_helper->DelEdgeBT(*edge.prev);
      }break;
    case _splitVert:
      {
        v = m_helper->FindVertice(vt);
        if(m_helper->IsFound())
        {
          fe._begin = vt;
          fe._end   = v;
          //m_diagonals.push_back(fe);
          m_diagonals.insert(fe);
          m_helper->UpdateCurrEgde(vt);
        }
        m_helper->AddEdgeBT(edge);
        m_helper->UpdateEgde(edge, vt);
      }break;
    case _mergeVert:
      {
        v = m_helper->GetHelper(*edge.prev);
        if(v._type == _mergeVert)
        {
          fe._begin = vt;
          fe._end   = v;
          //m_diagonals.push_back(fe);
          m_diagonals.insert(fe);
        }
        m_helper->DelEdgeBT(*edge.prev);
        v = m_helper->FindVertice(vt);
        if(m_helper->IsFound())
        {
          if(v._type == _mergeVert)
          {
            fe._begin = vt;
            fe._end   = v;
            //m_diagonals.push_back(fe);
            m_diagonals.insert(fe);
          }
          m_helper->UpdateCurrEgde(vt);
        }
      }break;
    case _regularVert:
      {
        if(edge._begin.y > edge._end.y) //The interior of P lies on the right of edge
        {
          v = m_helper->GetHelper(*edge.prev);
          if(v._type == _mergeVert)
          {
            fe._begin = vt;
            fe._end   = v;
            //m_diagonals.push_back(fe);
            m_diagonals.insert(fe);
          }
          m_helper->DelEdgeBT(*edge.prev);
          m_helper->AddEdgeBT(edge);
          m_helper->UpdateEgde(edge, vt);
        }else //The interior of P lies on the left of edge
        {
          v = m_helper->FindVertice(vt);
          if(m_helper->IsFound())
          {
            if(v._type == _mergeVert)
            {
              fe._begin = vt;
              fe._end   = v;
              //m_diagonals.push_back(fe);
              m_diagonals.insert(fe);
            }
            m_helper->UpdateCurrEgde(vt);
          }
        }
      }break;
  }
}


bool Convex::CheckFigure()
{
  //TODO: Fill this prerequisities
  return true;
}

bool Convex::CheckDirection(const figureVertice & v1, const figureVertice & v2)
{
  LinearFunction linearf;
  POINT p,l;
  double   delta, subdelta;

  p.x = v1.x + (v2.x - v1.x)/2;
  p.y = v1.y + (v2.y - v1.y)/2;

  linearf.Create(v1,v2);
  linearf.GetSymetricFunction(linearf,p);

  //We are looking for a vector which has a length = 1 symetric to given 
  delta = (2 * p.x) + (2 * linearf.GetA() * linearf.GetB()) - (2 * linearf.GetA());
  delta = pow(delta,2);

  subdelta = 4 * ((pow(linearf.GetA(),2) + 1) * (pow((double)p.x,2) + pow(linearf.GetB(),2) + pow((double)p.y,2) - 2 * linearf.GetB() - 1));

  delta = delta - subdelta;

  subdelta = (sqrt(delta) - (2 * p.x + (2 * linearf.GetA() * linearf.GetB()))) / (2 * (pow(linearf.GetA(),2) + 1));
  
  //The subdelta is a x-coordinate of seeking vector

  l.x = subdelta;
  l.y = linearf.CalculateValue(l,0).y;

  //Now we have to check if given point is on the left or rigt side of given edge
  return true;
}




void Convex::SplitFigure2Face()
{
  //Configuration cc;
  //m_faceFactory
  diagonalListIterator it;
  figureEdge diagonal, *edge;
  edgeIterator it_beg,it_end,it_edge;
  
  m_faceFactory->Clean();


  HDC    hdc = GetDC(m_hWnd);

  for(it = m_diagonals.begin();
      it != m_diagonals.end();
      it ++)
  {
    //we get one by one the diagonals
    diagonal = *it;
    //if(cc.GetConfig(DRAW_DIAGONAL))
    //{
    MoveToEx(hdc,diagonal._begin.x - m_shift.x,diagonal._begin.y- m_shift.y,NULL);
    LineTo(hdc,diagonal._end.x - m_shift.x,diagonal._end.y - m_shift.y);
    //}
    
    
    if(m_diagonalsProcessed.find(diagonal) == m_diagonalsProcessed.end())
    {
      SetDiagonalDirection(diagonal);
      CreateFace(diagonal, true);
    }
   //The diagonal has changed the _begin and _end 
  }
  //Now we have to add the last face 
  edgeIterator edgeIt;

  Face * face = new Face();
  //figureEdge  edge;
  for(edgeIt = m_edgeList->begin();
      edgeIt != m_edgeList->end();
      edgeIt ++)
  {
    edge = reinterpret_cast<figureEdge *>(*edgeIt);
    face->AddEdge(*edge);
  }
  m_faceFactory->AddFace(face);

  //m_faceFactory->Test();
}


void Convex::CreateFace(figureEdge & diagonal, bool direction)
{
  figureEdge edge, next_diagonal;
  Face * face;

  //Set the begining and end of diagonal
  SetDiagonalDirection(diagonal);

  edge = FindEdge(diagonal._end, true);
 
  diagonal.prev = edge.prev;

  next_diagonal = diagonal;
  while(GetDiagonalPrecedesor(edge._begin, next_diagonal))
        CreateFace(next_diagonal,false);

  face = new Face();
  //Check if the diagonal is staretd on the end of found edge
  //but check also if the givent vertice is not equal of diagonal._end
  while(edge._end != diagonal._begin ) //&& direction)) // || (edge._begin != diagonal._begin && !direction)) //wrong condition
  {
  
    while(Check4Diagonal(edge._end, next_diagonal))
          CreateFace(next_diagonal,false);
    
    if(edge.prev->next != NULL)
      edge = *edge.prev->next;
    else
      edge = *edge.next->prev;
    //edge = *edge.next->prev;
    face->AddEdge(edge);
    
    //but we have to replace coordinates of beggining
    //edge.next->_begin = edge._begin; 
    
    //m_edgeList->remove((long long)edge.next->prev);
    //delete(edge.next->prev); //delete the current edge pointer
    m_edgeList4Search->insert(diagonalPair(diagonal,(long long)edge.next->prev));
     
    edge.next->prev = edge.prev;
    edge.prev->next = edge.next;
    edge = *edge.next;
    //edge.prev = diagonal.prev;
  }

  edge.next->prev->prev = diagonal.prev; //replace the link between
  diagonal.prev->next = edge.next->prev;
  edge.next->prev->_begin = diagonal._end; //The direction of diagonal is changed due to different face direction
  edge.next->prev->_end = diagonal._begin;
  //edge = *edge.next->prev;
  face->AddEdge(edge);

  face->AddEdge(diagonal);

  //remove from the list the current diagonal to ommit the search
  RemoveFromSearch(diagonal);
  //m_diagonals.erase(m_diagonals.find(diagonal));
  m_diagonalsProcessed.insert(diagonal);
  //Add face to FaceFactory
  m_faceFactory->AddFace(face);
}

bool Convex::Check4Diagonal(const figureVertice & v, figureEdge & ed)
{
  diagonalListIterator it;
  for(it = m_diagonals.begin();
      it != m_diagonals.end();
      it ++)
  {
    ed = (*it);
    if(m_diagonalsProcessed.find(ed) == m_diagonalsProcessed.end())
    {
      if((ed._begin == v ) || (ed._end == v ))
      {
       return true;
      }
    }
  }
  return false;
}





/*
void Prerequisities(const figureEdge & diagonal)
{
  figureVertice v;
  figureEdge    edge;
  //Set the begining and end of diagonal
  if(diagonal._begin.y < diagonal._end.y)
  {
    //swap the vertices of diagonal 
    v = diagonal._end;
    diagonal._end = diagonal._begin;
    diagonal._begin = v;
  }
  edge = FindEdge(diagonal._begin);
}
*/

void Convex::SetDiagonalDirection(figureEdge & diagonal)
{
  //We looking for shortest path via edges from begin of diagonal to the end or from end to begin
  //And based on this we will set the begin and end of diagonal

  figureVertice v1,v2;
  figureEdge    edge;
  unsigned int cost1, cost2;
  v1 = diagonal._begin;
  v2 = diagonal._end;
  
  //lets find a way from begin to end
  cost1 = 1;
  edge = FindEdge(v1, true);
  while(edge._end != v2 && cost1 < m_edgeList->size())
  {
    cost1++;
    edge = *edge.next;
  }

  cost2 = 1;
  edge = FindEdge(v2, true);
  while(edge._end != v1 && cost2 < m_edgeList->size())
  {
    cost2++;
    edge = *edge.next;
  }
  if(cost1 < cost2)
  {
    diagonal._begin = v2;
    diagonal._end   = v1;
  }
  diagonal.waycost = min(cost1,cost2); 
}





void Convex::RemoveFromSearch(const figureEdge & diagonal)
{
  diagonalIterator it;
  diagonalRange it_range;
  figureEdge diag_test;
  it_range = m_edgeList4Search->equal_range(diagonal);
  for(it = it_range.first;
      it != it_range.second;
      it ++)
  {
    diag_test = it->first;
    assert(diag_test == diagonal);
    m_edgeList->remove(it->second);
    delete((figureEdge *)(it->second)); //delete the current edge pointer
  }
  //m_edgeList4Search->clear();
}


bool Convex::GetDiagonalPrecedesor(const figureVertice & vertex, figureEdge & diagonal)
{
  diagonalListIterator it;
  figureVertice        v1, v2;
  int                  waycost;


  waycost = diagonal.waycost;
  v1 = diagonal._begin;
  v2 = diagonal._end;

  
  for(it = m_diagonals.begin();
      it != m_diagonals.end();
      it ++)
  {
    diagonal = (*it);
    
    if(m_diagonalsProcessed.find(diagonal) == m_diagonalsProcessed.end()) //the edge is not on the processed list
    {
      if((diagonal._begin == vertex ) || (diagonal._end == vertex ))
      {
        //We set the waycost for found diagonal
        SetDiagonalDirection(diagonal);
        //Now we found a diagonal
        //but we have to be sure it is different from passed one
        //and lays on the diagonal path so the best way is to find a 
        //a length of path and check if this one is shortest from 
        //passed diagonal
        if(diagonal.waycost < waycost)
          return true;
      }
    }
  }
  return false;
}

